home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / arith / iplace.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  9.1 KB  |  425 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  iplace.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. /*              iplace.c           RD, 24.09.91     */
  17. /*     Dies ersetzt irv.c!                */
  18.  
  19. #include <LEDA/impl/iint.h>
  20. #include <LEDA/impl/iloc.h>
  21.  
  22. #ifdef USE_DOUBLEPLACE
  23.  
  24. #ifdef __GNUC__
  25. PLACE PLACEadd(PLACE a, PLACE b, PLACE carry, PLACE *sum)
  26. #else
  27. PLACE PLACEadd(a, b, carry, sum)
  28.     PLACE a, b, carry, *sum;
  29. #endif
  30.     /* *sum=a+b+carry, return Uebertrag */
  31. {    register DOUBLEPLACE accu = 0;
  32.         accu = a;
  33.         accu += b;
  34.         accu += carry;
  35.         *sum = accu;
  36.         return accu >> LOGPLACE;
  37. }
  38.  
  39. #ifdef __GNUC__
  40. PLACE PLACEsub(PLACE a, PLACE b, PLACE carry, PLACE *diff)
  41. #else
  42. PLACE PLACEsub(a, b, carry, diff)
  43.         PLACE a, b, carry, *diff;
  44. #endif
  45.     /* *diff=a-b-carry, return Uebertrag 0 oder 1 */
  46. {       register DOUBLEPLACE accu = 0;
  47.         accu = a;
  48.         accu -= b;
  49.         accu -= carry;
  50.         *diff = accu;
  51.         accu >>= LOGPLACE;
  52.         return accu & 1;
  53. }
  54.  
  55. #ifdef __GNUC__
  56. PLACE PLACEmuladd(PLACE a, PLACE b, PLACE carry, PLACE *paccu)
  57. #else
  58. PLACE PLACEmuladd(a, b, carry, paccu)
  59.     PLACE a, b, carry, *paccu;
  60. #endif
  61.     /* *paccu=*paccu+a*b+carry, return Uebertrag */
  62. {       register DOUBLEPLACE accu = 0;
  63.         accu = a;
  64.         accu *= b;
  65.         accu += *paccu;
  66.         accu += carry;
  67.         *paccu = accu;
  68.         return accu >> LOGPLACE;
  69. }
  70.  
  71. #ifndef __PARC__
  72. #ifdef __GNUC__
  73. PLACE PLACEmul(PLACE a, PLACE b, PLACE carry, PLACE *paccu)
  74. #else
  75. PLACE PLACEmul(a, b, carry, paccu)
  76.         PLACE a, b, carry, *paccu; 
  77. #endif
  78.     /* *paccu=a*b+carry, return Uebertrag */
  79. {       register DOUBLEPLACE accu = 0;
  80.         accu = a;
  81.         accu *= b;
  82.         accu += carry;
  83.         *paccu = accu;
  84.         return accu >> LOGPLACE;
  85. }
  86. #endif
  87.  
  88. #ifdef __GNUC__
  89. PLACE PLACEmulsub(PLACE a, PLACE b, PLACE carry, PLACE *paccu) 
  90. #else
  91. PLACE PLACEmulsub(a, b, carry, paccu) 
  92.         PLACE a, b, carry, *paccu; 
  93. #endif
  94.     /* *paccu=*paccu-a*b-carry, return Uebertrag */
  95. {       register SDOUBLEPLACE saccu = 0;
  96.     register DOUBLEPLACE prod;
  97.         prod = a;
  98.         prod *= b;
  99.         prod += carry;
  100.         saccu = *paccu;
  101.     saccu-=(PLACE) prod;
  102.     prod>>=LOGRADIX;
  103.     *paccu=saccu;
  104.     saccu>>=LOGRADIX;
  105.     prod += (saccu & 1);
  106.         return prod;
  107. }
  108.  
  109. #ifndef __PARC__
  110. #ifdef __GNUC__
  111. PLACE PLACEdiv(PLACE h, PLACE l, PLACE n, PLACE *q)
  112. #else
  113. PLACE PLACEdiv(h, l, n, q)
  114.     PLACE h, l, n, *q;
  115. #endif
  116.     /* h*RADIX+l / n ergibt Quotient *q, return Rest */
  117.         /* Division mit Rest
  118.               Voraussetzung:     h < n                */
  119. {       register DOUBLEPLACE accu = 0;
  120.         accu = (h<<LOGPLACE) | l;
  121.         *q = accu / n;
  122.         return accu % n;
  123. }
  124. #endif
  125. #endif
  126.  
  127. /**************************************************************/
  128.  
  129. #ifdef USE_IF_IN_ADD_AND_SUB
  130.  
  131. PLACE PLACEadd(a, b, carry, sum)
  132.     PLACE a, b, carry, *sum;
  133.     /* *sum=a+b+carry, return Uebertrag */
  134. {    PLACE accu;
  135.         accu = a + b + carry;
  136.         *sum = accu;
  137.     if (accu < a)
  138.         return 1;
  139.     else
  140.         return 0;
  141. }
  142.  
  143. PLACE PLACEsub(a, b, carry, diff)
  144.         PLACE a, b, carry, *diff;
  145.     /* *diff=a-b-carry, return Uebertrag 0 oder 1 */
  146. {       PLACE accu;
  147.         accu = a-b-carry;
  148.         *diff = accu;
  149.     if (accu > a)
  150.         return 1;
  151.     else
  152.         return 0;
  153. }
  154.  
  155. #endif
  156.  
  157. #ifndef USE_SPARC_ASM
  158. #ifdef sparc
  159. #ifndef USE_DOUBLEPLACE
  160.  
  161. #define LPM1 (LOGPLACE-1)
  162.  
  163. PLACE PLACEdiv(h, l, n, q)
  164.     PLACE h, l, n, *q;
  165.     /* h*RADIX+l / n ergibt Quotient *q, return Rest */
  166.         /* Division mit Rest
  167.               Voraussetzung:     h < n                */
  168. {       register PLACE qd = 0, carry;
  169.     register int i;
  170.     for (i=0; i<LOGPLACE; i++) {
  171.         carry=h>>LPM1;
  172.         h = (h<<1) | (l>>LPM1);
  173.         l = l<<1;
  174.         qd<<=1;
  175.         if (carry || h>=n) {
  176.             qd+=1;
  177.             h-=n;
  178.     }    }
  179.     *q = qd;
  180.     return h;
  181. }
  182.  
  183. #endif
  184. #endif
  185. #endif
  186.  
  187. /***************************************************************/
  188.  
  189. #ifndef ATARI
  190. BOOLEAN veceq(a, b, count)
  191.         register PLACE *a, *b; 
  192.         register int count;
  193.         /* return a[count]==b[count]; */
  194. {       for ( ; count>0; count--)
  195.                 if (*a++ != *b++)
  196.                         return FALSE;
  197.         return TRUE;
  198. }
  199. #endif
  200.  
  201. #ifndef ATARI
  202. BOOLEAN vecgt(a, b, count)
  203.         register PLACE *a, *b; 
  204.         register int count;
  205.         /* return a[count]>b[count] lexikographisch */
  206. {       for (a+=count, b+=count; count>0; count--) {
  207.         register PLACE aa, bb;
  208.         aa=*--a;
  209.         bb=*--b;
  210.                 if (aa > bb)
  211.                         return TRUE;
  212.                 else if (aa < bb)
  213.                         return FALSE;
  214.     }
  215.         return FALSE;
  216. }
  217. #endif
  218.  
  219. #ifndef ATARI
  220. #ifndef __PARC__
  221. BOOLEAN vecsr1(u, l)
  222.     register PLACE * u;
  223.     register int l;
  224. /*    b=u[l]%2; u[l]/=2; return b; */
  225. {    register PLACE b, bold, c;
  226.     u=u + l;
  227.     bold=0;
  228.     while(l) {
  229.         b=*--u;
  230.         c=b>>1;
  231.         c|=(bold<<(LOGRADIX-1));
  232.         bold=b;
  233.         *u=c;
  234.         l--;
  235.     }
  236.     b&=1;
  237.     return (BOOLEAN) b;
  238. }        /* vecsr1 */
  239. #endif
  240. #endif
  241.  
  242. #ifndef __PARC__
  243. #ifndef ATARI
  244. void vecsri(u, l, i)
  245.     register PLACE * u;
  246.     register int l;
  247.     register int i;
  248. /*    b=u[l]%2^i; u[l]/=2^i;     i<LOGRADIX */
  249. {    register PLACE b, bold, c;
  250.     u=u + l;
  251.     bold=0;
  252.     while(l) {
  253.         b=*--u;
  254.         c=b>>i;
  255.         c|=(bold<<(LOGRADIX-i));
  256.         bold=b;
  257.         *u=c;
  258.         l--;
  259.     }
  260. }        /* vecsri */
  261. #endif
  262. #endif
  263.  
  264. /**************************************************************/
  265.  
  266. #ifndef USE_DOUBLEPLACE
  267.  
  268. int cvadd(sum, a, b, counta, countb)
  269.         register pPLACE sum, a, b; 
  270.         register int counta, countb;
  271.         /* sum[]=a[counta]+b[countb]; 
  272.        sum soll auch Uebertraege fassen */
  273. {       register PLACE carry=0;
  274.     register int countmax;
  275.     if (counta>countb) {
  276.         countmax=counta;
  277.         counta-=countb;
  278.             for ( ; countb>0; countb--)
  279.             carry=PLACEadd(*a++, *b++, carry, sum++);
  280.             for ( ; counta>0; counta--)
  281.             carry=PLACEadd(*a++, 0, carry, sum++);
  282.     } else {
  283.         countmax=countb;
  284.         countb-=counta;
  285.             for ( ; counta>0; counta--)
  286.             carry=PLACEadd(*a++, *b++, carry, sum++);
  287.             for ( ; countb>0; countb--)
  288.             carry=PLACEadd(0, *b++, carry, sum++);
  289.         }
  290.     *sum=carry;
  291.     if (carry)
  292.         return countmax+1;
  293.     else
  294.         return countmax;
  295. }    /* cvadd */
  296.  
  297. #ifndef USE_SPARC_ASM
  298. void cvecsubto(a, b, count)
  299.         register PLACE *a, *b; 
  300.         register int count;
  301.         /* a[]-=b[count]; a muss groesser oder gleich b sein */
  302. {       register PLACE carry=0;
  303.         for ( ; count>0; count--) {
  304.         carry=PLACEsub(*a, *b++, carry, a);
  305.         a++;
  306.     }
  307.         while (carry) {
  308.         carry=PLACEsub(*a, 0, carry, a);
  309.         a++;
  310.     }
  311. }        /* cvecsubto */
  312. #endif
  313.  
  314. int cvsub(diff, a, b, counta, countb)
  315.     register pPLACE diff, a, b;
  316.     register int counta, countb;
  317.     /* diff[]=a[counta]-b[countb]; a>=b */
  318. {       register PLACE carry=0;
  319.     register int l=counta;
  320.     counta-=countb;
  321.     for ( ; countb>0; countb--)
  322.         carry=PLACEsub(*a++, *b++, carry, diff++);
  323.     while (carry) {
  324.         carry=PLACEsub(*a++, 0, carry, diff++);
  325.         counta--;
  326.     }
  327.     for ( ; counta>0; counta--) {
  328.         *diff++=*a++;
  329.     }
  330.     diff--;
  331.     while ((l>0)&&(! *diff)) {
  332.         diff--;
  333.         l--;
  334.     }
  335.     return l;
  336. }        /* cvsub */
  337.  
  338. PLACE vecaddto(a, b, count)
  339.         register PLACE *a, *b; 
  340.         register int count;
  341.         /* a[count]+=b[count]; return carry; */
  342. {       register PLACE carry=0;
  343.         for ( ; count>0; count--) {
  344.         carry=PLACEadd(*a, *b++, carry, a);
  345.         a++;
  346.     }
  347.         return carry;
  348. }
  349.  
  350. PLACE vecsubto(a, b, count)
  351.         register PLACE *a, *b; 
  352.         register int count;
  353.         /* a[count]-=b[count]; return carry; 0 oder 1 */
  354. {       register PLACE carry=0;
  355.         for ( ; count>0; count--) {
  356.         carry=PLACEsub(*a, *b++, carry, a);
  357.         a++;
  358.     }
  359.         return (carry & 1);
  360. }
  361.  
  362. #ifdef __GNUC__
  363. PLACE vecdiv(PLACE *q, PLACE *a, PLACE d, int count)
  364. #else
  365. PLACE vecdiv(q, a, d, count)
  366.         register PLACE *q, *a;
  367.     register PLACE d;
  368.         register int count;
  369. #endif
  370.         /* q[count]=a[count]/d; return a[count]%d; */
  371. {       register PLACE carry=0;
  372.         for (q+=count, a+=count; count>0; count--)
  373.         carry=PLACEdiv(carry, *--a, d, --q);
  374.         return carry;
  375. }
  376.  
  377. #ifdef __GNUC__
  378. PLACE vecmul(PLACE *product, PLACE *a, PLACE m, int count)
  379. #else
  380. PLACE vecmul(product, a, m, count)
  381.         register PLACE *product, *a, m;
  382.         register int count;
  383. #endif
  384.         /* product[count]=m*a[count]; return carry; */
  385. {       register PLACE carry=0;
  386.         for ( ; count>0; count--)
  387.         carry=PLACEmul(*a++, m, carry, product++);
  388.         return carry;
  389. }        /* vecmul */
  390.  
  391. #ifndef USE_SPARC_ASM
  392. #ifdef __GNUC__
  393. PLACE vecmuladd(PLACE *paccu, PLACE *a, PLACE m, int count)
  394. #else
  395. PLACE vecmuladd(paccu, a, m, count)
  396.         register PLACE *paccu, *a, m; 
  397.         register int count;
  398. #endif
  399.         /* paccu[count] += m*a[count]; return carry; */
  400. {       register PLACE carry=0;
  401.         for ( ; count>0; count--) {
  402.          carry=PLACEmuladd(*a++, m, carry, paccu++);
  403.         }
  404.         return carry;
  405. }        /* vecmuladd */
  406. #endif
  407.  
  408. #ifdef __GNUC__
  409. PLACE vecmulsub(PLACE *paccu, PLACE *a, PLACE m, int count)
  410. #else
  411. PLACE vecmulsub(paccu, a, m, count)
  412.         register PLACE *paccu, *a, m;
  413.         register int count;
  414. #endif
  415.         /* paccu[count+1] -= m*a[count]; return carry; 
  416.         carry ist 0 oder 1 */
  417. {    register PLACE carry=0;
  418.         for ( ; count>0; count--)
  419.         carry=PLACEmulsub(*a++, m, carry, paccu++);
  420.     carry=PLACEsub(*paccu, carry, 0, paccu);
  421.         return carry;
  422. }
  423.  
  424. #endif
  425.